#include <stdio.h>

// 函数声明
int findMode(int *arr, int size);
int majorityElement(int *nums, int numsSize);

int main() {
    // 给定整数数组
    //int arr[] = {1, 1, 3, 1, 1, 5, 1, 7, 8, 9, 10, 11, 12, 13, 14, 15};
    int arr[] = {1, 1, 3, 1, 1, 5, 1};
    int size = sizeof(arr) / sizeof(arr[0]);

    // 调用函数找出众数并打印结果
    int candidate = findMode(arr, size);
    if (candidate < 0) {
        printf("findMode, no candidate\n");
    }
    else {
        printf("findMode, The candidate of the array is: %d\n", arr[candidate]);
    }

    candidate = majorityElement(arr, size);
    if (candidate < 0) {
        printf("majorityElement, no candidate\n");
    }
    else {
        printf("majorityElement, The candidate of the array is: %d\n", arr[candidate]);
    }

    return 0;
}

// 函数定义：找出整数数组中的众数
int findMode(int *arr, int size)
{
    int maxCount = 0; // 最大出现次数
    int mode = 0;     // 众数
    int currentCount; // 当前数字出现次数
    int pos = 0;

    // 遍历数组中的每个数字
    for (int i = 0;  i < size;  i++) {
        currentCount = 0;

        // 统计当前数字在数组中出现的次数
        for (int j = 0;  j < size;  j++) {
            if (arr[j] == arr[i]) {
                currentCount++;
            }
        }

        // 如果当前数字的出现次数大于最大出现次数，则更新最大出现次数和众数
        if (currentCount > maxCount) {
            maxCount = currentCount;
            mode = arr[i];
            pos = i;
        }
    }

    if (maxCount < (size / 2)) {
    // 没有出现次数超过半数的数
        return -1;
    }

    return pos;
}


int majorityElement(int *nums, int numsSize)
{
    int candidate = nums[0];
    int count = 1;
    int pos = 0;

    for (int i = 1;  i < numsSize;  i++) {
        if (candidate == nums[i]) {
            count++;
        }
        else {
            count--;
            if (0 == count) {
                count = 1;
                candidate = nums[i];
                pos = i;
            }
        }
    }

    if (count < (numsSize / 2)) {
    // 没有出现次数超过半数的数
        return -1;
    }
    return pos;
}
